package leetcode_100;

/**
 *@author 周杨
 *SearchinRotatedSortedArrayII_81 从一个旋转过的有序数组里查找某一个数  要求时间复杂度为O(logN)
 *describe: 用二分查找的思想 每次确定有序数组区间 并判断此数是否在此区间内 AC 65%
 *2018年5月15日 下午12:39:51
 */
public class SearchinRotatedSortedArrayII_81 {
	int [] nums;
	int target;
	public static void main(String[] args) {
		int nums[]=new int[] {2,5,6,0,0,1,2};
		int nums1[]=new int[] {1,1,1,1};
		SearchinRotatedSortedArrayII_81 test=new SearchinRotatedSortedArrayII_81();
		System.out.println(test.search(nums1, 3));

	}
	
    public boolean search(int [] nums,int target) {
    	if(nums.length==0)
    		return false;
    	this.nums=nums;
    	this.target=target;
    	return binary(0,this.nums.length-1);
    }
    
    public boolean binary(int l,int r) {
    	if(nums[l]==this.target||nums[r]==this.target)
    		return true;
    	if(l==r) {//搜索范围是这一个
    		return this.target==nums[l];
    	}
    	if(nums[r]>nums[l]) {//有序了
    		if(this.target<nums[r]&&this.target>nums[l]) {//可能在此区间内
    			int mid=(r+l)/2;
    			if(!binary(l,mid)) {
    				return binary(mid+1,r);
    			}
    			return true;
    		}	
    		else
    			return false;
    	}
    	else {//仍然是无序
    		int mid=(r+l)/2;
    		if(!binary(l,mid))
    			return binary(mid+1,r);
    		return true;
    	}
    }
}
